package com.moter.demo01.niukeoffer.demo01;

/**
 * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * 用例通过率: 100.00% 运行时间: 102ms 占用内存: 17320KB
 * 题解思路 ： 在二分法的基础上 增加一些判断，
 * //运行一亿次 用时2751ms 比上一种稍微少了一点点，但是如果数据量大，差距会很明显
 * 二维长度n，一维长度m
 * 时间复杂度：O(n*log2m)
 * 空间复杂度：O(1)
 */
public class Solution02 {
    public static boolean Find(int target, int[][] array) {
        //如果数组为空，左上角元素大于target 右下角元素小于target直接返回false
        if (array.length == 0 || array[0].length == 0 || array[0][0] > target || array[array.length - 1][array[0].length - 1] < target)
            return false;
        for (int i = 0; i < array.length; i++) {
            if (array[i][0] > target || array[i][array[i].length - 1] < target)//如果每列第一个元素大于target，最后一个元素小于target，排除该行
                continue;
            if (FindByLine(target, array[i]))
                return true;
        }
        return false;
    }

    public static boolean FindByLine(int target, int[] array) {
        int start = 0;
        int end = array.length - 1;
        int mid;
        while (start <= end) {
            mid = (start + end) / 2;
            if (array[mid] == target)
                return true;
            else if (array[mid] > target)
                end = mid - 1;
            else
                start = mid + 1;
        }
        return false;
    }

    public static void main(String[] args) {//2751
        long start = System.currentTimeMillis();
        for (int i = 0; i < 100000000; i++) {
            Find(11, new int[][]{{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}});
        }
        System.out.println(System.currentTimeMillis() - start);
    }
}
